package 笔试真题;

import java.util.*;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Tengxun1 {
    public static void main(String[] args) {
        Tengxun1 tengxun1 = new Tengxun1();
        ListNode root = new ListNode(0);
        ListNode node =root;
        node.next = new ListNode(7); node = node.next;
        node.next = new ListNode(8); node = node.next;
        node.next = new ListNode(13); node = node.next;
        node.next = new ListNode(11); node = node.next;
        node.next = new ListNode(15); node = node.next;
        node.next = new ListNode(10); node = node.next;
        node.next = new ListNode(15); node = node.next;
        node.next = new ListNode(0); node = node.next;
        node.next = new ListNode(9); node = node.next;
        node.next = new ListNode(9); node = node.next;
        ListNode[] solve = tengxun1.solve(9, root);
        System.out.println(1);
    }
    public ListNode[] solve(int m, ListNode a) {
        // write code here
        HashMap<Integer, List<ListNode>> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            map.put(i,new ArrayList<>());
        }
        while (a!=null){
            int p = a.val%m;
            List<ListNode> l =  map.get(p);
            l.add(a);
            a = a.next;
        }
        ListNode[] ans = new ListNode[m];
        int id = 0;
        for (Map.Entry<Integer, List<ListNode>> entry : map.entrySet()) {
            List<ListNode> value = entry.getValue();
            if(value.isEmpty()) id++;
            for (int i = 0; i < value.size(); i++) {
                if(i==0){
                    ans[id++] = value.get(i);
                }
                if(i<value.size()-1){
                    value.get(i).next = value.get(i+1);
                }else {
                    value.get(i).next = null;
                }
            }
        }
        return ans;
    }
}
